// 【数组中出现次数超过一半的数字】
//给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
public class Day_3_2_数组中超过一半的数字 {
    // 如果两个数不相等，就消去这两个数，每次消去一个众数和一个非众数，最后留下的一定是那个众数
    public int MoreThanHalfNum_Solution(int [] array) {
        int result = array[0];
        int flag = 1;
        for(int i = 1; i < array.length; i++){
            if(flag == 0){
                result = array[i];
                flag = 1;
            }
            if(result == array[i]){
                flag++;
            }else{
                flag--;
            }
        }
        return result;
    }
}
